package io.github.hadyang.leetcode.bytedance;

/**
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 *
 * <p>如果不存在公共前缀，返回空字符串 ""。
 *
 * <p>示例 1:
 *
 * <p>输入: ["flower","flow","flight"] 输出: "fl" 示例 2:
 *
 * <p>输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 说明:
 *
 * <p>所有输入只包含小写字母 a-z 。
 */
public class String1014 {
  public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) {
      return "";
    }

    int minLen = strs[0].length();
    for (String str : strs) {
      minLen = Math.min(minLen, str.length());
    }

    char[][] data = new char[strs.length][minLen];
    for (int i = 0; i < strs.length; i++) {
      char[] chars = strs[i].toCharArray();
      System.arraycopy(chars, 0, data[i], 0, minLen);
    }

    StringBuilder res = new StringBuilder();
    for (int i = 0; i < minLen; i++) {
      for (int j = 1; j < data.length; j++) {
        if (data[j - 1][i] != data[j][i]) {
          return res.toString();
        }
      }
      res.append(data[0][i]);
    }
    return res.toString();
  }

  public static void main(String[] args) {
    String1014 main = new String1014();

    System.out.println(main.longestCommonPrefix(new String[] {"flower", "flow", "flight"}));
    System.out.println(main.longestCommonPrefix(new String[] {"dog", "racecar", "car"}));
  }
}
